package com.c2b.algorithm.newcoder;

import java.util.ArrayList;

/**
 * <a href='https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6?tpId=295&tqId=23286&ru=%2Fexam%2Foj&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj'>BM5 合并k个已排序的链表</a>
 *
 * @author c2b
 * @since 2024/3/14 10:18
 */
public class BM5MergeKLists {

    public static class Solution {
        public ListNode mergeKLists(ArrayList<ListNode> lists) {
            // 假如有16个链表: 分为 8 8，8又分为 4 4，4又分为2和2，2个合并，后于两位合并后的合并，归并
            return merge(lists, 0, lists.size() - 1);
        }

        private ListNode merge(ArrayList<ListNode> lists, int left, int right) {
            if (right == left) {
                return lists.get(left);
            }
            if (left < right) {
                return null;
            }
            int mid = left + ((right - left) >> 1);
            return merge(merge(lists, left, mid), merge(lists, mid + 1, right));
        }

        private ListNode merge(ListNode listNode1, ListNode listNode2) {
            if (listNode1 == null) {
                return listNode2;
            }
            if (listNode2 == null) {
                return listNode1;
            }
            ListNode dummyHead = new ListNode(-1);
            ListNode currNode = dummyHead;
            while (listNode1 != null && listNode2 != null) {
                if (listNode1.val < listNode2.val) {
                    currNode.next = listNode1;
                    listNode1 = listNode1.next;
                } else {
                    currNode.next = listNode2;
                    listNode2 = listNode2.next;
                }
                currNode = currNode.next;
            }
            currNode.next = listNode1 != null ? listNode1 : listNode2;
            return dummyHead.next;
        }
    }
}
